<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // 回溯法的核心框架
      // for 选择 in 选择列表:
      // # 做选择
      // 将该选择从选择列表移除
      // 路径.add(选择)
      // backtrack(路径, 选择列表)
      // # 撤销选择
      // 路径.remove(选择)
      // 将该选择再加入选择列表

      var subsets = function (nums) {
        // 方法一：回溯（）---时间：O（）（不会算，至少是n!，要回溯递归）---空间：O（）（不会算，至少是n，递归栈的深度）
        // let track = [];
        // let res = [];
        // backtrack(nums, 0);
        // return res;

        // function backtrack(nums, start) {
        //   // debugger;
        //   // 直接push不行,得这样
        //   // 前序位置，每个节点的值都是一个子集
        //   res.push([...track]);
        //   for (let i = start; i < nums.length; i++) {
        //     track.push(nums[i]);
        //     // 通过 start 参数控制树枝的遍历，避免产生重复的子集
        //     backtrack(nums, i + 1);
        //     track.pop();
        //   }
        // }

        // 方法二：迭代（每增加一个元素，让之前幂集中的每个集合，追加这个元素，就是新增的子集）---时间：O（）（）---空间：O（）（）
        // const res =[]
        // res.push([])
        // for(let i=0;i<nums.length;i++){
        //   const length = res.length
        //   for(let j=0;j<length;j++){
        //     const arr = [...res[j]]
        //     arr.push(nums[i])
        //     res.push([...arr])
        //   }
        // }
        // return res

        // 方法三：位运算（https://leetcode.cn/problems/subsets/solutions/420294/zi-ji-by-leetcode-solution/）---时间：O（）（）---空间：O（）（）
        // 不太理解
        const ans = [];
        const n = nums.length;
        for (let i = 0; i < (1 << n); i++) {
          const t = [];
          for (let j = 0; j < n; j++) {
            if (i & (1 << j)) {
              t.push(nums[j]);
            }
          }
          ans.push(t);
        }
        return ans;
      };

      console.log(subsets([1, 2, 3]));
    </script>
  </body>
</html>
